# A bloody large number.
INFINITY = 1.0e400
from time import clock

class TimeOutException(Exception):
    pass


class AlphaBetaSearch:
    '''
    This search algorithm implements the limited-resource minimax tree search 
    algorithm with alpha-beta pruning for zero-sum games. This version cuts off 
    search by depth alone and uses an evaluation function (utility).
    '''
    
    
    def __init__(self, player, utility, time_limit = INFINITY, w=1, v=0):
        '''
        Constructor.
        
        @param player: Your player. This search algorithm will choose the best
                       actions for this player.
        @param max_depth: The depth of the search tree.
        @param utility: An evaluation function for states.
        '''
        self.bf_counter = []
        self.time_limit = time_limit
        self.player = player
        self.utility = utility
        self.w = w
        self.v = v
    
    def search(self, current_state):
        self.start_time = clock()
        items = current_state.getSuccessors().items()
        self.bf_counter.append(len(items))
        print 'items before',len(items)
        res = items[0][0]
        try:
            if self.v == 0:
                items = sorted(items, key=lambda i: -self.utility(i[1],self.start_time))
            items = items[:int(len(items)*self.w)+1]
            res = items[0][0]
            print 'sort is',str(clock() - self.start_time)
            #print 'item first',self.utility(items[0][1],self.start_time),' - item last',self.utility(items[-1][1],self.start_time)
            self.max_depth=1
            while True:
                test = clock()
                self.max_depth += 1
                res = self.searchItration(current_state, items)
                print 'depth=' + str(self.max_depth) + ' time=' + str(clock()-test)

        except TimeOutException:
            return res
                
            
            
    
    def searchItration(self, current_state, items):
        '''
        Search game to determine best action; use alpha-beta pruning.
        
        @param current_state: The current game state to start the search from.
        '''
        best_value = -INFINITY

        
        t = []

        for action, state in items:
            test = clock()
            value_fn = self._getValueFn(state)
            value = value_fn(state, best_value, INFINITY, 1)
            if value > best_value:
                best_value = value
                best_action = action
            t.append(clock() - test)
        print max(t),'*******************************'
        return best_action
    
    def _getValueFn(self, state):
        if state.getCurrentPlayer() == self.player:
            return self._maxValue
        else:
            return self._minValue
    
    def _cutoffTest(self, state, depth):
        if clock() - self.start_time > self.time_limit - 0.5:
                raise TimeOutException()
        return depth >= self.max_depth or (state.getWinner() is not None) 
    
    def _maxValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state,self.start_time)
        
        value = -INFINITY
        values = state.getSuccessors().values()
        self.bf_counter.append(len(values))
        if self.v == 0:
            values = sorted(values, key=lambda v: -self.utility(v,self.start_time))
        values = values[:int(len(values)*self.w)+1]
        for successor in values:
            value_fn = self._getValueFn(successor)
            value = max(value, value_fn(successor, alpha, beta, depth + 1))
            if value >= beta:
                return value
            alpha = max(alpha, value)
        
        return value
    
    def _minValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state,self.start_time)
        
        value = INFINITY
        values = state.getSuccessors().values()
        self.bf_counter.append(len(values))
        if self.v == 0:
            values = sorted(values, key=lambda v: -self.utility(v,self.start_time))
        values = values[:int(len(values)*self.w)+1]
        for successor in values:
            value_fn = self._getValueFn(successor)
            value = min(value, value_fn(successor, alpha, beta, depth + 1))
            if value <= alpha:
                return value
            beta = min(beta, value)
        
        return value